package leetcode100;

// TODO 二分查找 [经典] 【-】 在排序数组中查找元素的第一个和最后一个位置
// TODO https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/solution/by-pandaoknight-51pt/

public class lc100_0034 {

    public int[] searchRange(int[] nums, int target) {
        int n = nums.length;
        int leftRange = searchLeft(nums, target, n);  // 查找左边界
        int rightRange = searchRight(nums, target, n);  // 查找右边界
        return new int[]{leftRange, rightRange};  // 返回左右边界数组
    }

    private int searchLeft(int[] nums, int target, int n) {
        int left = 0, right = n - 1;  // 右边界
        while (left <= right) {
            int mid = (left + right) / 2;  // 计算中间位置
            if ((nums[mid] == target && mid == 0) || (nums[mid] == target && nums[mid-1] != target)) {
                return mid;
            }
            if (nums[mid] >= target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;  // 返回右边界
    }

    private int searchRight(int[] nums, int target, int n) {
        int left = 0, right = n - 1;  // 右边界
        while (left <= right) {
            int mid = (left + right) / 2;  // 计算中间位置
            if ((nums[mid] == target && mid == n-1) || (nums[mid] == target && nums[mid+1] != target)) {
                return mid;
            }
            if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;  // 返回右边界
    }
}